package com.lz.learning.dc;

import java.util.Arrays;

/**
 * 算法 第四版
 */
public class BaseMerge {
    // 不要在 merge 函数里构造新数组了，因为 merge 函数会被多次调用，影响性能
    // 直接一次性构造一个足够大的数组，简洁，高效
    private static Comparable[] aux;

    public static void sort(Comparable[] a) {
        aux = new Comparable[a.length];
        // sort(a, 0, a.length - 1);
        sort02(a, 0, a.length - 1);

    }

    /**
     * 从顶到下
     * @param a
     * @param lo
     * @param hi
     */
    private static void sort(Comparable[] a, int lo, int hi) {
        if (lo >= hi) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, lo, mid);
        sort(a, mid + 1, hi);
        merge(a, lo, mid, hi);
    }

    /**
     * 从底到上
     * @param a
     * @param lo
     * @param hi
     */
    private static void sort02(Comparable[] a, int lo, int hi) {
        // 子数组大小
        for (int i = 1; i < a.length; i += i) {
            // 索引
            for (int j = 0; j < a.length - i; j += 2 * i) {
                merge(a, j, j + i - 1, Math.min(j + 2 * i - 1, a.length - 1));
            }
        }
    }
    private static void merge(Comparable[] a, int lo, int mid, int hi) {
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++)
            aux[k] = a[k];
        for (int k = lo; k <= hi; k++) {
            // i超出界线，直接将另一部分，复制上去
            if (i > mid) {
                a[k] = aux[j++];
            } else if (j > hi) {
                a[k] = aux[i++];
                // 比较左右最大值
            } else if (less(aux[j], aux[i])) {
                a[k] = aux[j++];
            } else {
                a[k] = aux[i++];
            }
        }
    }

    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    public static void main(String[] args) {

        Integer[] ints = new Integer[]{1, 3, 5, 3, 784, 96, 35, 25, 78, 0, 4, 1, 6, 8};

        sort(ints);

        Dc dc = new Dc();
        // int[] ints1 = {1, 3, 5, 3, 784, 96, 35, 25, 78, 0, 4, 1, 6, 8};
        int[] ints1 = {7,2,3, 1, 5, 4};
        dc.sort(ints1);
        System.out.println(Arrays.toString(ints1));
    }

    /**
     * Dc int版本
     */
    static class Dc {
        int[] aux;
        void sort(int[] array) {
            if (array == null || array.length < 1) return;
            aux = new int[array.length];
            sort0(array, 0, array.length - 1);

        }
        private void sort0(int[] array, int lo, int hi) {
            // 结束条件
            if (hi <= lo) return;
            int mid = lo + (hi - lo) / 2;
            sort0(array, lo, mid);
            sort0(array, mid + 1, hi);
            merge0(array, lo, mid, hi);
        }

        private void merge0(int[] array, int lo, int mid, int hi) {
            for (int k = lo; k <= hi; k++) {
                aux[k] = array[k];
            }

            int i = lo, j = mid + 1;
            for (int k = lo; k <= hi; k++) {
                // Note: i,j 做比较
                if (i > mid)
                    array[k] = aux[j++];
                else if (j > hi)
                    array[k] = aux[i++];
                // Note: aux
                else if (aux[i] >aux[j])
                    array[k] = aux[j++];
                else
                    array[k] = aux[i++];

            }


        }


    }
}